import java.util.LinkedList;

public class Prime {
    // https://oi-wiki.org/math/number-theory/sieve/#%E5%87%8F%E5%B0%91%E5%86%85%E5%AD%98%E7%9A%84%E5%8D%A0%E7%94%A8

    public static void main(String[] args) {
        eratosthenes(100).forEach(System.out::println);
        eratosthenes_sqrt(100).forEach(System.out::println);
        euler(100).forEach(System.out::println);
    }

    /**
     * O(nloglogn)
     * @param n
     * @return
     */
    public static LinkedList<Integer> eratosthenes(int n) {
        LinkedList<Integer> primes = new LinkedList<>();
        boolean[] is_prime = new boolean[n + 1];
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i <= n; i++) {
            is_prime[i] = true;
        }
        for (int i = 2; i <= n; i++) {
            if (is_prime[i]) {
                primes.add(i);
                if ((long) i * i > n)
                    continue;

                // 因为2到i-1的倍数都筛过了，从i的倍数开始筛，提高筛选速度
                for (int j = i * i; j <= n; j += i) {
                    is_prime[j] = false;
                }
            }
        }
        return primes;
    }

    public static LinkedList<Integer> eratosthenes_sqrt(int n) {
        LinkedList<Integer> primes = new LinkedList<>();
        boolean[] is_prime = new boolean[n + 1];
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i <= n; i++) {
            is_prime[i] = true;
        }
        for (int i = 2; i * i <= n; i++) {
            if (is_prime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    is_prime[j] = false;
                }
            }
        }
        for (int i = 2; i <= n; i++) {
            if (is_prime[i])
                primes.add(i);
        }
        return primes;
    }

    /**
     * O(n)
     * @param n
     * @return
     */
    public static LinkedList<Integer> euler(int n) {
        LinkedList<Integer> primes = new LinkedList<>();
        boolean[] not_prime = new boolean[n + 1];
        for (int i = 2; i < n + 1; i++) {
            if (!not_prime[i]) {
                primes.add(i);
            }
            for (int pri_j : primes) {
                if (i * pri_j > n)
                    break;
                not_prime[i * pri_j] = true;
                if (i % pri_j == 0)
                    // i是pri_j的倍数，i的倍数一定会被pri_j筛掉，因而break
                    // pri_j是i的最小质因子
                    break;
            }
        }
        return primes;
    }
}
